#ifndef UHM_UTIL_SORT_HXX_
#define UHM_UTIL_SORT_HXX_

namespace uhm {

  // DO NOT USE THIS SORT.... TOO SLOW... 

  //! Compare two entities with operator <
  template<class T_> Bool_ compare(T_ &a, T_ &b) { return ( a < b ); }

  //! Swap the two object v1, v2.
  // Swapping involves operator=, this may cause a trouble when we swap matrices.
  // I use shallow copy and set matrices not created but share buffers.
  // So, do not use sorting for array of matrices.
  template<class T_> void exchange(T_ &v1,T_ &v2) { T_ temp=v2;    v2=v1;    v1=temp;  }

  //! quick sort based on the given ordering function.
  template<class T_> void quicksort(T_ array[], Int_ hi, Int_ lo,
                                    Bool_ (*order)(T_&, T_&)) {
    while (hi>lo) {
      Int_ i=lo;
      Int_ j=hi;
      do {
        while ( order(array[i], array[lo]) && i<j )
          ++i;
        while ( order(array[lo], array[--j]) )
          ;
        if (i<j) exchange(array[i],array[j]);
      } while (i<j);

      exchange( array[lo], array[j] );

      if(j-lo>hi-(j+1)) {

        if ( (hi-lo) > UHM_SEQUENTIAL_SORT_SIZE ) {

#pragma omp task firstprivate(j, lo)
          quicksort(array, j-1, lo, order);
          lo = j + 1;
        } else {
          quicksort(array, j-1, lo, order);
          lo = j + 1;
        }
      } else {

        if ( (hi-lo) > UHM_SEQUENTIAL_SORT_SIZE ) {

#pragma omp task firstprivate(j, hi)
          quicksort(array, hi, j+1, order);
          hi = j - 1;
        } else {
          quicksort(array, hi, j+1, order);
          hi = j - 1;
        }
      }
    }

    //! quick sort does not put taskwait here. 
  }

}

#endif


